#include <bits/stdc++.h>

using namespace std;

// N皇后问题
// 测试链接 : https://leetcode.cn/problems/n-queens/

class Solution 
{
private:
    vector<string> path;
    vector<vector<string>> ret;

    void dfs1(int limit, int col, int left, int right, int i)
    {
        if(col == limit)
        {
            ret.emplace_back(path);
            return;
        }

        int ban = col | left | right;
        int candidate = limit & (~ban);
        int place = 0;
        while(candidate)
        {
            place = candidate & (-candidate);
            path[i][log2(place)] = 'Q';
            candidate ^= place;
            dfs1(limit, col | place, (left | place) >> 1, (right | place) << 1, i + 1);
            path[i][log2(place)] = '.';
        }
    }

    bool check(vector<int>& record, int i, int j)
    {
        for(int k = 0; k < i; ++k)
        {
            if(record[k] == j || abs(i - k) == abs(j - record[k])) return false;
        }
        return true;
    }

    void dfs2(int i, int n, vector<int>& record)
    {
        if(i == n)
        {
            ret.emplace_back(path);
            return;
        }

        for(int j = 0; j < n; ++j)
        {
            if(check(record, i, j))
            {
                path[i][j] = 'Q';
                record[i] = j;
                dfs2(i + 1, n, record);
                path[i][j] = '.';
            }
        }
    }

public:
    vector<vector<string>> solveNQueens(int n) 
    {
        path.resize(n, string(n, '.'));
        int limit = (1 << n) - 1;
        dfs1(limit, 0, 0, 0, 0);
        return ret;
    }

    vector<vector<string>> solveNQueens2(int n) 
    {
        path.resize(n, string(n, '.'));
        vector<int> record(n);
        dfs2(0, n, record);
        return ret;
    }
};